package com.peng.leetcode.tree;

import java.util.ArrayDeque;

/**
 * BSTIterator2
 * 173. 二叉搜索树迭代器
 * https://leetcode.cn/problems/binary-search-tree-iterator/
 * <p>
 * Created on 2022/12/7
 *
 * @author lupeng
 */
public class BSTIterator2 {

    class BSTIterator {

        ArrayDeque<TreeNode> q = new ArrayDeque<>();

        public BSTIterator(TreeNode root) {
            while (root != null) {
                q.offerFirst(root);
                root = root.left;
            }
        }

        public int next() {
            TreeNode curr = q.pollFirst();
            TreeNode n = curr.right;
            while (n != null) {
                q.offerFirst(n);
                n = n.left;
            }
            return curr.val;
        }

        public boolean hasNext() {
            return !q.isEmpty();
        }
    }
}
